package huawei.study;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class HuaWei16 {

    /**
     * 华为机试 HJ16
     * 其本质是0-1背包问题
     * https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tags=&title=&difficulty=0&judgeStatus=0&rp=1
     * @param args
     */
    public static void main(String[] args) throws Exception{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String s = buf.readLine();
        String[] ss = s.split(" ");
        int totalMoney = Integer.parseInt(ss[0]);
        int prodNum = Integer.parseInt(ss[1]);
        int[][] prices = new int[prodNum][4];
        int[][] weights = new int[prodNum][4];
        int count = 0;
        while ((s = buf.readLine()) != null){
            ss = s.split(" ");
            int price = Integer.parseInt(ss[0]);
            int weight = Integer.parseInt(ss[1]);
            int master = Integer.parseInt(ss[2]);
            if (master == 0){
                prices[count][0] = price;
                weights[count][0] = weight * price;
                for (int i = 1; i < 3; i++){
                    if (prices[count][i] != 0){
                        prices[count][i] += prices[count][0];
                        weights[count][i] += weights[count][0];
                    } else {
                        break;
                    }
                }
                count++;
            } else {
                for (int i = 1; i < 3; i++){
                    if (prices[master - 1][i] == 0){
                        prices[master - 1][i] = price + prices[master - 1][0];
                        weights[master - 1][i] = weight * price + weights[master - 1][0];
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < count; i++){
            if (prices[i][1] != 0 && prices[i][2] != 0){
                prices[i][3] = prices[i][1] + prices[i][2] - prices[i][0];
                weights[i][3] = weights[i][1] + weights[i][2] - weights[i][0];
            }
        }
        //进行动态规划求解
        int[][] dp = new int[count + 1][totalMoney + 1];
        //进行初始化

        //进行动态规划求值
        for (int i = 1; i <= count; i++){
            for (int j = 1; j <= totalMoney; j++){
                dp[i][j] = dp[i - 1][j];
                for (int n = 0; n < 4; n++){
                    int weight = weights[i - 1][n];
                    int price = prices[i - 1][n];
                    if (j >= price && price != 0){
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - price] + weight);
                    }
                }
            }
        }

        System.out.println(dp[count][totalMoney]);
    }
}
